# SelectionSort20211017.py

# 选择排序
#              v current_idx 用于标记把找到的最小值放到哪里
# [8, 5, 2, 9, 6, 3] 对于整个数组来说，最小值应该放在位置 0
# [MIN, 8, 5, 9, 6, 3] 对于这个剩下的数组来说，最小值应该放在位置 1
# [MIN, MIN1, MIN2, MIN3, MIN4, 6] 对于这个剩下的数组来说，最小值应该放在位置 2

def selection_sort(array):

  current_idx = 0

  while current_idx < len(array) - 1:
    smallest_idx = current_idx

    for i in range(current_idx + 1, len(array)):
      if array[smallest_idx] > array[i]:
        smallest_idx = i

    array[current_idx], array[smallest_idx] = array[smallest_idx], array[current_idx]
    current_idx += 1

  return array

print(selection_sort([8, 5, 2, 9, 6, 3]))